package leetcode;

/**
 * leet code 1
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 *
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 *
 * Example:
 *
 * Given nums = [2, 7, 11, 15], target = 9,
 *
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 */


import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static void main(String... arg) {
        int[] nums = {2, 7, 11, 15};
        int[] res1 = twoSum_hash(nums, 9);
        for (int i : res1) {
            System.out.print(i+"_");
        }
        System.out.println("");
        int[] res2 = twoSum_nesting(nums, 9);
        for (int i : res2) {
            System.out.print(i+"_");
        }
    }



    /**
     * by hash
     * On*logn
     * 3ms
     */
    public static int[] twoSum_hash(int[] nums, int target) {
        Map hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            Integer diff = target - nums[i];
            if (hash.containsKey(diff)) {
                int[] res = {(int) hash.get(diff), i};
                return res;
            }
            hash.put(nums[i], i);

        }
        int[] res = {-1, -1};
        return res;
    }
    /**
     * by for nesting
     * On*n
     * 42ms
      */

    public static int[] twoSum_nesting(int[] nums, int target) {

        for(int  i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if((nums[i]+nums[j])==target){
                    int[] res = {i,j};
                    return res;
                }
            }
        }
        int[] res = {-1,-1};
        return res;


    }
}
